package com.LeetCode.Graph;

import org.junit.Test;

import java.util.*;

/**
 * A* 算法
 * 启发函数 h 通常使用 曼哈顿距离 (manhattan distance)
 * 顶点之间的路径长度 g
 * 估计函数 f(i) = g(i) + h(i)
 *
 */
public class AStar {
    //路径顶点类
    private class Vertex{
        int id;
        int dist;//起始顶点到这点的距离
        int f;// 启发函数
        int x, y;//该点在地图中的坐标，用于生成路径
        Map<Integer, Vertex> vertices;
        public Vertex(int id, int x, int y){
            this.id = id;
            this.x = x;
            this.y = y;
            this.f = Integer.MAX_VALUE;
            this.dist = Integer.MAX_VALUE;
            vertices = new HashMap<>();
        }

        public void addVertex(int id, int x, int y){
            vertices.putIfAbsent(id ,new Vertex(id, x, y));
        }

    }

    public int getManHattanDistance(int x1, int y1, int x2, int y2){
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    int  e_x, e_y;

    int n, m;

    List<int[]> res;

    boolean[][] visited;

    char[][] grid;

    public List<int[]> AStarFindPath(char[][] grid, int[] start, int[] end){
        int s_x = start[0];
        int s_y = start[1];
        this.e_x = end[0];
        this.e_y = end[1];
        this.n = grid.length;
        this.m = grid[0].length;
        this.res = new ArrayList<>();
        this.visited = new boolean[n][m];
        this.grid = grid;
        bfs(s_x, s_y);
        return res;
    }

    int[][] dist = {{0,1},{1,0},
            {0,-1},{-1,0}};

    boolean canReach = false; // 标记可达

    public void bfs(int start_x, int start_y){
        Queue<int[]> queue = new LinkedList<>();
        if(grid[start_x][start_y] == '#')
            return;
        queue.offer(new int[]{start_x, start_y});
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int cur_x = cur[0];
            int cur_y = cur[1];
            if(cur_x == e_x && cur_y == e_y){
                canReach = true;
                return;
            }
            int cur_min = Integer.MAX_VALUE;
            int min_x = 0;
            int min_y = 0;

            int failCount = 0;

            for(int i = 0; i<4; i++){
                int nx = cur_x + dist[i][0];
                int ny = cur_y + dist[i][1];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] || grid[nx][ny] == '#'){
                    failCount++;
                    if(failCount == 4){
                        break;
                    }
                    continue;
                }

                int f = getManHattanDistance(nx, ny, e_x, e_y);
                if(f < cur_min){
                    min_x = nx;
                    min_y = ny;
                    cur_min = f;
                }
            }
            if(failCount != 4){
                queue.offer(new int[]{min_x, min_y});
                visited[min_x][min_y] = true;
                res.add(new int[]{min_x, min_y});
            }
        }

    }

    @Test
    public void test(){
        char[][] grid = {
                {'0','0','#','0','0'},
                {'#','0','0','0','#'},
                {'0','#','#','0','0'},
                {'0','0','#','0','0'},
                {'#','0','#','#','0'},
        };
        AStarFindPath(grid,new int[]{0,0}, new int[]{4,4}).forEach(e ->{
            System.out.println(e[0] + " " + e[1]);
        });


    }


}
